'''
https://leetcode.cn/problems/factor-combinations
'''

from typing import List


class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        res = []
        path = []

        def f(n, start):
            if n == 1:
                if path:
                    res.append(path + [start])
                return
            sqrt_num = int(n ** 0.5)
            for factor in range(start, sqrt_num + 1):
                if n % factor: continue
                path.append(factor)
                f(n // factor, factor)
                path.pop()
            f(1, -1)        # 主动 call base case
        f(n, 2)
        return res